# -*- coding:utf-8 -*-
# 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
# 你应当 保留 两个分区中每个节点的初始相对位置。

# 示例 1：
# 输入：head = [1,4,3,2,5,2], x = 3
# 输出：[1,2,2,4,3,5]

# 示例 2：
# 输入：head = [2,1], x = 2
# 输出：[1,2]
 

# 提示：
# 链表中节点的数目在范围 [0, 200] 内
# -100 <= Node.val <= 100
# -200 <= x <= 200


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
class Solution:
    def partition(self, head, x: int) -> ListNode:
        guard = ListNode(0, None)
        guard.next = head
        insert = guard
        it = guard
        while it.next != None:
            if it.next.val >= x:
                it = it.next
                continue
            if insert == it:
                it = it.next
                insert = insert.next
                continue
            t = insert.next
            insert.next = it.next
            it.next = it.next.next
            insert.next.next = t
            insert = insert.next
        return guard.next

h = ListNode(1, None)
h.next = ListNode(4, None)
h.next.next = ListNode(3, None)
h.next.next.next = ListNode(2, None)
h.next.next.next.next = ListNode(5, None)
h.next.next.next.next.next = ListNode(2, None)


t = Solution()
print(t.partition(h, 3))